package algorithm.linear;

/**
 * 求解素数环问题
 * 将n个自然数（1-n）排列成环形，使得每相邻两数之和为素数，构成一个素数环。
 *
 * 思路：
 * 将1放入素数环，再对2-n自然数K依次测试其与素数环最后一个元素之和是否为素数
 * 若是则将k加入到素数环中，否则无法处理，必须等待再次测试
 * 因此需要设置一个队列用于存放暂时无法处理的自然数。
 * 直到队列为空
 *
 * params：
 * ring是存放素数环元素的线性表
 * q是链式队列
 * isPrime判断是否为素数
 */
public class PrimeRing {
    public static void main(String[] args) {
        new PrimeRing(10);
    }

    public PrimeRing(int n){
        //创建一个顺序表存储素数环
        SeqList<Integer> ring = new SeqList<Integer>(n);
        //1特殊优先增加到素数环中
        ring.add(new Integer(1));
        System.out.println(" ring:"+ring.toString());
        LinkedQueue<Integer> q =  new LinkedQueue<Integer>();
        //2~n入列
        for(int i = 2;i<=n;i++) {
            q.enqueue(new Integer(i));
        }
        int i = 0;
        while (!q.isEmpty()){
            int k = q.dequeue().intValue();
            System.out.println("i:"+i+" k:"+k+" ring:"+ring.toString());
            //相邻两数这和为素
            if (isPrime(ring.get(i)+k)){
                i++;
                ring.add(new Integer(k));
            }
            else {
                q.enqueue(new Integer(k));
            }
            System.out.println(q.toString());
        }
        System.out.println("i>"+i);
        System.out.println(q.toString());
        System.out.println(ring.toString());
    }

    //判断k是否为素数
    public boolean isPrime(int k) {
        if (k  == 1)
            return false;
        if (k == 2)
            return true;
        if ( k< 2|| k>2 && k%2==0)
            return false;
        //返回k的平方根
        /*for( int i =3; i< Math.sqrt(k); i+=2){
            if( k % i == 0){
                return false;
            }
        }
        return true;*/
        //或
        /*int j = (int) Math.sqrt(k);
        if ( j%2 == 0)
            j--;//获取测试范围最大的奇数
        while (j>2 && k%j != 0)
            j-=2;
        return j<2;*/
        for(int i=2;i<=Math.sqrt(k);i++){
            if(k%i == 0)
                return false;
        }
        return true;
    }
}
